



<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 13, Exercise 13<BR>

<BR>

</H1>





We shall assume that the profits are of type <code class=code>float</code>

or <code class=code>int</code>.  First we define a class

<code class=code>object</code> which is used to sort the objects into

nondecreasing order of profit density.  Following the sort, the objects are

to be packed into the knapsack in the reverse of this order.

The class

<code class=code>object</code> is given below and in the file

<code class=code>object2.h</code>.



<HR class = coderule>

<pre class = code>

class Object {

   friend float Knapsack(int [], int [], int, int, int []);

   public:

      operator float() const

      {return d;}

   private:

      int ID;  // object identifier

      float d; // profit density

};

<hr class=coderule>

</pre>

<br><br>



The function

<code class=code>Knapsack</code> packs the objects into the knapsack

in nonincreasing order of profit density.  It returns the profit

generated by the greedy packing.  It also sets <code class=code>x[i]</code>

to 1 if object <code class=code>i</code> is packed

into the knapsack and to 0 if object <code class=code>i</code>

is not packed into the knapsack.



<HR class = coderule>

<pre class = code>

template&lt;class Tw, class Tp&gt;

float Knapsack(Tp p[], Tw w[], Tw c, int n, int x[])

{// Return value of greedy knapsack filling. 

 // Set x[i] = 1 iff object i included in knapsack,

 // 1 &lt;= i &lt;= n.

   float P = 0;  // will be sum of profits



   // define an object array to be sorted by

   // profit density

   Object *Q = new Object [n+1];



   for (int i = 1; i &lt;= n; i++) {

      // array of profit densities

      Q[i].ID = i;

      Q[i].d = 1.0*p[i]/w[i];

      }



   // sort by density

   HeapSort(Q,n);



   // load in nonincreasing order of density

   for (int i = n; i &gt; 0; i--) {

      int id = Q[i].ID;

      if (w[id] &lt;= c ) {// object id fits

         x[id] = 1;

         c -= w[id];

         P += p[id];

         }

      else // object id does not fit

         x[id] = 0;

      }



   delete [] Q;

   return P;

}

<HR class = coderule>

</pre>

<br><br>



The above code together with test data and output appear in the files

<code class=code>aknap.*</code>.

</dl>



</FONT>

</BODY>

</HTML>

